package cn.edu.xjtu.work.numRescueBoats;

import java.util.Arrays;

/**
 * 881. 救生艇
 * 
 * 第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
 * 
 * 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
 * 
 * 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
 */
public class Solution {
  public static void main(String[] args) {
    int[] people = { 3, 5, 3, 4 };
    Solution solu = new Solution();
    System.out.println(solu.numRescueBoats(people, 5));
  }

  public int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int left = 0;
    int right = people.length - 1;
    int ret = 0;
    while (left < right) {
      while (left < right && people[left] + people[right] > limit) {
        right--;
        ret++;
      }
      ret++;
      left++;
      right--;
    }
    if (left == right) {
      ret++;
    }
    return ret;
  }
}
